The present invention concerns allocation of quantities affecting performance for multicarrier communication systems. The present invention more particularly concerns, for example, processes that are capable of producing an optimal power allocation in such communication systems, an optimal bit allocation and/or an optimal performance margin allocation.
High speed data communication over both wired and wireless transmission media can be accomplished using various multicarrier communication methods in which a channel is divided into many subchannels that are essentially independent and free of intersymbol interference (ISI). Phase and/or amplitude modulation are used to increase the number of symbols which can be transmitted per unit time in the multicarrier communication methods.
A signal constellation is a communication method defined by points on a phase map that indicate the particular phase and amplitude for various symbols encoded by the method. As an example, an 8 PSK signal constellation has all its information encoded in phase, with 8 possible values per unit time at 45 degree phase separations. That amount of information encoding can be doubled by also having two possible amplitudes. Various encoding schemes known in the art are accurately described by their signal constellations.
Separations in phase and amplitude must be adequately maintained in a physical realization of coding points in a given signal constellation to avoid excessive coding errors. This is because the signal constellation imposes limits on the decoding side, which must determine, based upon received phase and amplitude information, which symbol is intended in a given transmission interval. Accordingly, given some power budget, it must be determined how power and bits are allocated to each subchannel to maximize performance under the restrictions that the signal constellations place on the system. This optimization is done to use power efficiently and to perform as well as a single channel solution. Because typical multicarrier systems can currently have as many as 256 channels and further increases are likely, the power allocation problem becomes complex, rendering fast allocation in real time difficult. The problem is further rendered difficult by the discrete nature of typically used integer-bit constellations that render the optimal power allocation solution to be a solution of a discontinuous integer programming problem, one that is difficult to solve by direct methods.
Other signal constellations of interest are those not having the integer-bit constellation restraint. Consider, for example, the alternate signaling scheme of 5 bits/symbol followed by 4 bits/symbol. This obtains a half bit granularity of 4.5 bits/symbol. Reported half bit improvements of up to 1 dB indicate the promise of half bit granularity. These constellations share the allocation problems of the integer-bit restrained constellations described above. Prior methods for power, bit and margin allocation have addressed these problems, in part, but typical methods either fail to reach optimal solutions or have a high computational cost of solution.
An exemplary method is commonly known as the Hughes-Hartog Algorithm, and is the subject of U.S. Pat. Nos. 4,679,227, 4,731,816 and 4,833,706, all of which are incorporated by reference in their entirety. This algorithm achieves an optimal power allocation. It begins by assigning no power and no bits to each of the subchannels. Then the subchannel which requires the least amount of power to increase its data rate is given that amount of power and that process is repeated until the power budget is exhausted. The algorithm accordingly has a slow convergence to solution and has an associated high computational cost.
Another known type of method is the subject of U.S. Pat. Nos. 5,479,447 and 5,400,322, both of which are incorporated by reference in their entirety. These algorithms use nearest-neighbor approximations and round the estimated bit allocations to integer numbers. Computational costs are less than in the Hughes-Hartog algorithm, but these methods do not present an ability to guarantee an optimal solution where one is desired. The ""322 patent updates power and bit allocations after slight changes in channel condition, but still is only capable of guaranteeing a suboptimal solution because of the generally ad hoc approach to arrive at a solution that lacks any theoretical basis for being optimal.
Other methods are disclosed in U.S. Pat. No. 5,598,435 (incorporated by reference in its entirety) to improve upon the previously known Hughes-Hartog and nearest-neighbor approaches through extension to the case of noninteger bits/symbols. These methods nonetheless share the aforementioned drawbacks of their predecessors. The improvement on Hughes-Hartog still has significant computational expenses, while the improvement on nearest-neighbor approaches lacks any ability to guarantee an optimal solution. Other types of methods which have significant computational expense as a result of a large required number of iterations are disclosed in U.S. Pat. Nos. 5,495,484 and 5,521,906, both of which are incorporated by reference in their entirety.
Thus, there is a need for an improved allocation method for multicarrier communication systems which addresses the aforementioned drawbacks. It is an object of the invention to provide such an improved method which has a computational cost suitable to real time application of the method and which can produce an optimal solution when such solution is desirable.
These and other objects and needs are met or exceeded by the present power allocation method. The method utilizes efficient look-up table searches and a Lagrange multiplier section division search to provide a capability to converge to the optimal solution. The total cost of the algorithm is 0(N) where N=the number of subchannels. Minimizing the Lagrange cost for the multiplier xcex which merges rate and power in a given subchannel results in a slope xcex that corresponds to the optimal power allocation for some total power budget. The cost is minimized when rate and power for each subchannel are chosen to correspond to the point on the rate versus power curve at slope xcex. Similarly, a bit or margin allocation may be obtained by solving for xcex on an appropriate curve. As used herein and in the art, curves constitute a discrete set of points representing, for example, a group of rate-power combinations. Associated values of xcex for a particular point are a continuous range.
The present invention renders the determination of the appropriate xcex from its range of values to be one of a low computational cost for bit, power or margin allocation. A particular xcex is evaluated to find its corresponding total power, followed by an update of values defining a range surrounding xcex, in the form of an increase or decrease, to get closer to the optimal solution. The updated or new slope xcex is defined by the quotient of the difference between high and low power divided by the difference between the high and low rate. Each xcex is evaluated to find the optimal operating point for each subchannel on the rate-power curve by summing the power allocated to the subchannels, and comparing the result to the power budget. Look-up tables are stored for individual channels, but similarity between channels (due to commonality of signal constellations) permits joint use of look-up tables by multiple channels. The tables are used to determine the rate-power characteristics at each iteration. An optimal solution is guaranteed when either a newly chosen power allocation meets the power budget exactly or a newly chosen power budget equals the high or low power of a previous iteration. Margin optimization is also achieved through the invention through the update process, where the update is conducted to converge upon a target bit rate as opposed to a target power budget.